In a wide variety of computing and communication systems information is stored in memory. A standard random access memory includes many memory address locations, some of which contain information. With conventional indexing schemes the data content of a memory cell is used with a hash or index to produce the address location of the data. The address has no real or direct relationship with the information contained in the data. In some applications, memory size is too large to practically address and access data using the conventional schemes. With large memories, an alternative technique for storing and accessing data is desired. Some of suitable alternative methods are termed content addressable memories or CAMs.
One application of content addressable memory is the storage of output ports based on Internet Protocol addresses. When a message arrives at a line card of an Internet Protocol router, the Internet Protocol address is examined. The message's target output port is based on the IP address. The current standard address is a binary sequence of the form {b0, b1, . . . , bNmax−1}, with Nmax=232, so that the total number of Internet Protocol version 4 (IPv4) addresses is currently 232. The number in base 10 is approximately 4 billion. A conventional memory with an address size of this magnitude is impractical for efficient access. Accordingly, some type of content addressable memory is generally used. Plans are in place to greatly expand the number of Internet Protocol addresses. The proposed Internet Protocol address standard version 6 (IPv6) sets Nmax to 2128, an increase to 2128 Internet Protocol addresses. The address size increase greatly elevates the storage and accessing complexity.
The number of entries in a target output lookup system grows with the number of output ports. The number of copies of the memory grows with the number of input ports. Therefore, for systems with a large number of ports, an answer to the problem of output port lookup based on Internet Protocol address is desired.
Various techniques have been devised to address storage complexity. For example, “Routing Lookups in Hardware at Memory Access Speeds”, by Pankaj Gupta, Steven Lin and Nick McKeown. IEEE INFOCOM April 1998, vol. 3 pp. 1240-1247, San Francisco, USA, describes a data system that can be used effectively in looking up an Internet Protocol address (IPv4) provided that one has a particular data structure available. Unfortunately, the reference does not have a complete solution to the efficient construction and maintenance of the data structures.